package mylib.dir;

/**
 * Created with IntelliJ IDEA.
 * User: 1
 * Date: 16.07.12
 * Time: 20:58
 * To change this template use File | Settings | File Templates.
 */
public class StringUtils {
    public static int[][] prefixAutomat(String s, int alphabet, char minSymbol) {
        int[] p = prefixFunction(s);
        int[][] ans = new int[p.length + 1][alphabet];
        for (int i = 0; i < p.length + 1; ++i)
            for (int sym = 0; sym < alphabet; ++sym)
                if (i > 0) {
                    if (i < s.length() && s.charAt(i) - minSymbol == sym) {
                        ans[i][sym] = i + 1;
                    } else {
                        if (p[i - 1] > 0)
                            ans[i][sym] = ans[p[i - 1]][sym];
                        else
                            ans[i][sym] = s.charAt(0) - minSymbol == sym ? 1 : 0;
                    }
                } else {
                    ans[i][sym] = s.charAt(0) - minSymbol == sym ? 1 : 0;
                }
        return ans;
    }

    public static int[] prefixFunction(String s) {
        int[] p = new int[s.length()];
        int cur = 0;
        for (int i = 1; i < p.length; ++i) {
            while (cur > 0 && s.charAt(i) != s.charAt(cur))
                cur = p[cur - 1];
            if (s.charAt(cur) == s.charAt(i))
                ++cur;
            p[i] = cur;
        }
        return p;
    }

    public static String reverse(String s) {
        StringBuilder sbl = new StringBuilder(s);
        sbl = sbl.reverse();
        return sbl.toString();
    }

    public static String[] removeEmptyEntry(String[] s) {
        int c = 0;
        for (String value : s) if (value.length() > 0) ++c;
        String[] res = new String[c];
        c = 0;
        for (String value : s) if (value.length() > 0) res[c++] = value;
        return res;
    }

    public static int[] suffixArray(String s) {
        int[] tmp = new int[s.length()];
        for (int i = 0; i < tmp.length; ++i) {
            tmp[i] = s.charAt(i);
        }
        return SuffixArray(tmp);
    }

    public static int compare(String a, String b, PolyHash pa, PolyHash pb, int la, int ra,
                              int lb, int rb) {
        int lcp = lcp(a, b, pa, pb, la, ra, lb, rb);
        if (la + lcp > ra) return -1;
        if (lb + lcp > rb) return 1;
        return Character.compare(a.charAt(la + lcp), b.charAt(lb + lcp));
    }

    public static int lcp(String a, String b, PolyHash pa, PolyHash pb, int la, int ra,
                          int lb, int rb) {
        int l = 1, r = Math.min(ra - la + 1, rb - lb + 1), res = 0;
        while (l <= r) {
            int check = (l + r) / 2;
            if (pa.getHash(la, la + check - 1) == pb.getHash(lb, lb + check - 1)) {
                res = Math.max(res, check);
                l = check + 1;
            } else {
                r = check - 1;
            }
        }
        return res;
    }

    public static int[] lcp(int[] p, String s) {
        int n = s.length();
        s = (s + s);
        int[] res = new int[p.length - 1];
        HashInfo info = new HashInfo(s.length());
        PolyHash polyHash = new PolyHash(s.toCharArray(), info);
        for (int i = 0; i < res.length; ++i) {
            System.gc();
            res[i] = lcp(s, s, polyHash, polyHash, p[i], p[i] + n - 1,
                    p[i + 1], p[i + 1] + n - 1);
        }
        return res;
    }

    public static int[] SuffixArray(int[] _a) {
        int[] a = _a.clone();
        int minAlpha = Integer.MAX_VALUE;
        int maxAlpha = Integer.MIN_VALUE;
        for (int x : a) {
            minAlpha = Math.min(minAlpha, x);
            maxAlpha = Math.max(maxAlpha, x);
        }
        int Alphabet = maxAlpha - minAlpha + 1;
        int[] count = new int[Alphabet];
        for (int i = 0; i < a.length; ++i)
            a[i] -= minAlpha;
        for (int x : a)
            count[x]++;
        int classes = 0;
        int n = a.length;
        int[] perm = new int[n];
        int[] c = new int[n];
        int[] pointer = new int[n];
        int[] sum = new int[Alphabet];
        for (int i = 0; i < Alphabet; ++i) {
            if (i > 0)
                sum[i] += sum[i - 1];
            sum[i] += count[i];
        }
        int[] ptr = new int[Alphabet];
        int[] first = new int[Alphabet];
        for (int i = 0; i < Alphabet; ++i) {
            if (count[i] > 0) {
                first[i] = classes;
                pointer[classes] = ptr[i] = (i == 0 ? 0 : sum[i - 1]);
                ++classes;
            }
        }
        for (int i = 0; i < n; ++i) {
            c[i] = first[a[i]];
            perm[ptr[a[i]]++] = i;
        }
        int[] nextp = new int[n];
        int[] nextc = new int[n];
        for (int h = 1; h < n && classes != n; h *= 2) {
            for (int j : perm) {
                int u = (j - h);
                if (u < 0) u += n;
                nextp[pointer[c[u]]++] = u;
            }
            classes = 0;
            for (int i = 0, j = 0; i < n; i = j) {
                for (j = i; j < n && c[nextp[j]] == c[nextp[i]] && c[(nextp[j] + h) % n] == c[(nextp[i] + h) % n]; ++j)
                    ;
                for (int u = i; u < j; ++u)
                    nextc[nextp[u]] = classes;
                pointer[classes] = i;
                classes++;
            }
            System.arraycopy(nextc, 0, c, 0, nextc.length);
            System.arraycopy(nextp, 0, perm, 0, nextp.length);
        }
        return perm;
    }

}
